高级排序算法基数排序

基数排序是什么？

基数排序是非比较排序算法，算法的时间复杂度是 $O(n)$

基数排序（Radix Sort）属于分配式排序，又称 "桶子法"（Bucket Sort 或 Bin Sort），将要排序的元素分配到某些 "桶" 中，以达到排序的作用。

相比于快速排序的 $O(nlgn)$ ,从表面上看具有不小的优势，但事实上可能有些出入，因为基数排序的 n 可能具有比较大的系数 K。因此在具体的应用中，应首先对这个排序函数的效率进行评估。（如果变化范围大的就不太适用了）

基数排序的方式可以采用最低位优先 LSD（Least sgnificant digital）法或最高位优先 MSD（Most sgnificant digital）法，LSD 的排序方式由键值的最右边开始，而 MSD 则相反，由键值的最左边开始。

LSD 的基数排序适用于位数小的数列，如果位数多的话，使用 MSD 的效率会比较好，MSD 的方式恰与 LSD 相反，是由高位数为基底开始进行分配，其他的演算方式则都相同。

以 LSD 为例，假设原来有一串数值如下所示：

73, 22, 93, 43, 55, 14, 28, 65, 39, 81

首先根据个位数的数值，在走访数值时将它们分配至编号 0 到 9 的桶子中：

接下来将这些桶子中的数值重新串接起来，成为以下的数列：

收集过程：
81, 22, 73, 93, 43, 14, 55, 65, 28, 39

接着再进行一次分配，这次是根据十位数来分配：

接下来将这些桶子中的数值重新串接起来，成为以下的数列：

收集过程：
14, 22, 28, 39, 43, 55, 65, 73, 81, 93

这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。

整个过程如下图所示：

排序原理

为什么要从低位开始向高位排序？

如果要从高位排序，那么次高位的排序会影响高位已经排好的大小关系。在数学中，数位越高，数位值对数的大小的影响就越大。从低位开始排序，就是对这种影响的排序。数位按照影响力从低到高的顺序排序，数位影响力相同则比较数位值。

为什么同一数位的排序子程序要使用稳定排序？

稳定排序的意思是指，待排序相同元素之间的相对前后关系，在各次排序中不会改变。比如实例中具有十位数字 5 的两个数字 58 和 356, 在十位排序之前 356 在 58 之前，在十位排序之后，356 依然在 58 之前

稳定排序能保证，上一次的排序成果被保留，十位数的排序过程能保留个位数的排序成果，百位数的排序过程能保留十位数的排序成果。

代码实现

public class Main {
    public static void main(String[] args) {
        int[] arr = generateArray(20, 99);
        int[] arrCopy = Arrays.copyOf(arr, arr.length);

        radixSort(arrCopy, 100);

        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(arrCopy));
    }

    /**
     *
     * @param d 表示数组中最大的数有几个十进制位（例如传入 100 就表示数组里面的数最大不会超过 100）
     */
    private static void radixSort(int[] array, int d) {
        int n = 1; // 代表位数对应的数：1,10,100...
        int k = 0; // 单纯计数用，不用管
        int length = array.length;
        int[][] bucket = new int[10][length];//排序桶用于保存每次排序后的结果，这一位上排序结果相同的数字放在同一个桶里
        int[] order = new int[length];//用于保存每个桶里有多少个数字（就是当计数器用）
        while (n < d) {
            // 将数组 array 里的每个数字放在相应的桶里
            for (int num : array)  {
                int digit = (num / n) % 10;
                // 把数组里面对应的数存进桶里面（这里挺有意思的，使用 order 数组的计数作为二维数组的下标）
                bucket[digit][order[digit]] = num;
                order[digit]++;
            }

            // 将前一个循环生成的桶里的数据覆盖回原数组中（就是第一轮排好的数放回原数组）
            for (int i = 0; i < length; i++) {
                // 检查 order 数组的计数
                if (order[i] != 0) {
                    for (int j = 0; j < order[i]; j++) {
                        // 从桶里取回数据
                        array[k] = bucket[i][j];
                        k++;
                    }
                }
                // 计数器置0，用于下一次位排序
                order[i] = 0;
            }
            n *= 10;
            k = 0;//将k置0，用于下一轮保存位排序结果
        }

    }


    /**
     * 生成随机数组
     */
    public static int[] generateArray(int len, int max) {
        int[] arr = new int[len];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * max);
        }
        return arr;
    }
}

改进优化后的代码

参考左神的教程 2:06:20

public class RadixSort {
    public static void main(String[] args) {
        // int[] arr = new int[]{3, 9, 6, 7, 4, 3, 5, 8, 2};
        int[] arr = generateArray(10, 100);
        int[] arrCopy = Arrays.copyOf(arr, arr.length);

        radixSort(arrCopy);
        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(arrCopy));

        CompleteBinaryTree.TreeNode root = CompleteBinaryTree.Tool.createTree(arrCopy);
        CompleteBinaryTree.Print.PrintTreeNode(root);
    }

    public static void radixSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        radixSort(arr, 0, arr.length - 1, maxBits(arr));
    }

    /**
     * 求出数组中最大的十进制位
     */
    public static int maxBits(int[] arr) {
        int max = Integer.MIN_VALUE;
        // 找到最大的数
        for (int j : arr) {
            max = Math.max(max, j);
        }
        int res = 0;
        // 通过最大值除 10 来求出最大位数
        while (max != 0) {
            res++;
            max /= 10;
        }
        return res;
    }

    /**
     * 基数排序
     *
     * @param arr   数组
     * @param L     数组左边（这里只是限制数组中要排序的部分）
     * @param R     数组右边
     * @param digit 表示数组中最大的数有几个十进制位
     */
    public static void radixSort(int[] arr, int L, int R, int digit) {
        // 以十为基底
        final int radix = 10;
        int i = 0, j = 0;
        // 有多少个数准备多少个辅助空间（桶）
        int[] bucket = new int[R - L + 1];
        for (int d = 1; d <= digit; d++) { // 有多少位（最大有几个十进制位）就进出几次
            // 10 个空间
            // count[0] 当前位（d位）是 0 的数字有多少个
            // count[1] 当前位（d位）是 (0 和 1) 的数字有多少个
            // count[2] 当前位（d位）是 (0、1 和 2) 的数字有多少个
            // count[i] 当前位（d位）是 (0 ~ i) 的数字有多少个

            int[] count = new int[radix]; // count[0..9] 前缀和数组
            for (i = L; i <= R; i++) {
                j = getDigit(arr[i], d);
                count[j]++;
            }

            for (i = 1; i < radix; i++) {
                count[i] = count[i] + count[i - 1];
            }
            for (i = R; i >= L; i--) {
                j = getDigit(arr[i], d);
                bucket[count[j] - 1] = arr[i];
                count[j]--;
            }
            for (i = L, j = 0; i <= R; i++, j++) {
                arr[i] = bucket[j];
            }
        }
    }

    /**
     * 取得 x 这个值的第 d 位的数字
     */
    public static int getDigit(int x, int d) {
        return ((x / ((int) Math.pow(10, d - 1))) % 10);
    }


    /**
     * 生成随机数组
     */
    public static int[] generateArray(int len, int max) {
        int[] arr = new int[len];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * max);
        }
        return arr;
    }
}

排序负数

三种使用了桶的算法区别

基数排序 vs 计数排序 vs 桶排序

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

基数排序：根据键值的每位数字来分配桶
计数排序：每个桶只存储单一键值
桶排序：每个桶存储一定范围的数值

Reference

算法总结系列之五: 基数排序(Radix Sort) 基数排序（Radix Sort）

基数排序是什么？​

排序原理​

代码实现​

改进优化后的代码​

排序负数​

三种使用了桶的算法区别​

Reference​